package cn.javadog.algorithm.e1_100;


import java.util.LinkedList;
import java.util.Objects;

/**
 * 合并两个有序链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * @author Sprite
 */
public class Algorithm21 {
	public static void main(String[] args) {
	}


	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null) return l2;
		if (l2 == null) return l1;

		ListNode max =  l1.val>l2.val ? l1 : l2;
		ListNode min =  l1.val>l2.val ? l2 : l1;

		LinkedList<Integer> queue = new LinkedList<>();
		while (max != null){
			queue.add(max.val);
			max = max.next;
		}
		ListNode tmp = min;
		while (!queue.isEmpty()){
			Integer poll = queue.poll();
			while (true){
				if (poll >= tmp.val && Objects.nonNull(tmp.next) && poll<tmp.next.val){
					ListNode node = new ListNode(poll);
					node.next = tmp.next;
					tmp.next = node;
					tmp = tmp.next;
					break;
				}else if (Objects.nonNull(tmp.next)){
					tmp = tmp.next;
				}else {
					ListNode node = new ListNode(poll);
					tmp.next = node;
					break;
				}
			}
		}
		return min;
	}

	protected static class ListNode {
		int val;
		ListNode next;
		ListNode(int x) { val = x; }
	}
}
